public class PriorityQueue<T>
{
    private List<T> data;
    private Comparison<T> comparison;

    public int Count { get { return data.Count; } }

    public PriorityQueue(Comparison<T> comparison)
    {
        this.data = new List<T>();
        this.comparison = comparison;
    }
    public PriorityQueue(Comparison<T> comparison, int capacity)
    {
        this.comparison = comparison;
        this.data = capacity > 0 ? new List<T>(capacity) : new List<T>();
    }
    public void Clear()
    {
        data.Clear();
    }
    public void Enqueue(T item)
    {
        data.Add(item);
        int childIndex = data.Count - 1;
        while (childIndex > 0)
        {
            int parentIndex = (childIndex - 1) / 2;
            if (comparison(data[childIndex], data[parentIndex]) >= 0)
                break;
            
            T tmp = data[childIndex];
            data[childIndex] = data[parentIndex];
            data[parentIndex] = tmp;
            childIndex = parentIndex;
        }
    }



    public T Dequeue()
    {
        if (data.Count == 0)
            throw new InvalidOperationException("PriorityQueue is empty");

        int lastIndex = data.Count - 1;
        T frontItem = data[0];
        data[0] = data[lastIndex];
        data.RemoveAt(lastIndex);

        lastIndex--;
        int parentIndex = 0;
        while (true)
        {
            int childIndex = parentIndex * 2 + 1;
            if (childIndex > lastIndex)
                break;

            int rightChild = childIndex + 1;
            if (rightChild <= lastIndex && comparison(data[rightChild],data[childIndex]) < 0)
                childIndex = rightChild;

            if (comparison(data[parentIndex],data[childIndex]) <= 0)
                break;

            T tmp = data[parentIndex];
            data[parentIndex] = data[childIndex];
            data[childIndex] = tmp;
            parentIndex = childIndex;
        }

        return frontItem;
    }

    public T Peek()
    {
        if (data.Count == 0)
            throw new InvalidOperationException("PriorityQueue is empty");
        return data[0];
    }

    public bool Contains(T item)
    {
        return data.Contains(item);
    }

    public List<T> ToList()
    {
        return new List<T>(data);
    }

    public bool IsConsistent()
    {
        if (data.Count == 0) return true;
        for (int parentIndex = 0; parentIndex < data.Count / 2; parentIndex++)
        {
            int leftChildIndex = 2 * parentIndex + 1;
            int rightChildIndex = 2 * parentIndex + 2;

            if (leftChildIndex < data.Count && 
                comparison(data[parentIndex],data[leftChildIndex]) > 0)
                return false;

            if (rightChildIndex < data.Count && 
                comparison(data[parentIndex],data[rightChildIndex]) > 0)
                return false;
        }
        return true;
    }
}